#include <iostream>
#include <string>
#include <vector>
using namespace std;

//class Solution {
//public:
//    static vector<string> letterCombinations(string digits)
//    {
//        
//        vector<string> str = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
//        vector<string> mystr;
//        int len = digits.size();
//
//        int arr[4] = { 0 };
//        for (int i = 0; i < len; i++)
//        {
//            arr[i] = digits[i] - '0';
//        }
//
//        
//        if (len == 2)
//        {
//            int count = 0;
//            for (int i = arr[0]; i < str[arr[0]].size(); i++)
//            {
//                for (int j = arr[1]; j < str[arr[1]].size(); j++)
//                {
//                    mystr[count++] += str[i][j];
//                }
//            }
//        }
//        else if (len == 3)
//        {
//            int count = 0;
//            vector<string> temp;
//
//            for (int i = 0; i < str[arr[0]].size(); i++)
//            {
//                for (int j = 0; j < str[arr[1]].size(); j++)
//                {
//                    temp[count++] += str[i][j];
//                }
//            }
//
//            int count2 = 0;
//            for (int i = 0; i < count; i++)
//            {
//                for (int j = 0; j < str[arr[2]].size(); j++)
//                {
//                    mystr[count2] += temp[i];
//                    mystr[count2++] += str[arr[2]][j];
//                }
//            }
//        }
//        else if (len == 4)
//        {
//            int count = 0;
//            vector<string> temp;
//
//            for (int i = 0; i < str[arr[0]].size(); i++)
//            {
//                for (int j = 0; j < str[arr[1]].size(); j++)
//                {
//                    temp[count++] += str[i][j];
//                }
//            }
//
//            int count2 = 0;
//            vector<string> temp2;
//
//            for (int i = 0; i < count; i++)
//            {
//                for (int j = 0; j < str[arr[2]].size(); j++)
//                {
//                    temp2[count2] += temp[i];
//                    temp2[count2++] += str[arr[2]][j];
//                }
//            }
//
//            int count3 = 0;
//            for (int i = 0; i < count2; i++)
//            {
//                for (int j = 0; j < str[arr[3]].size(); j++)
//                {
//                    mystr[count3] += temp2[i];
//                    mystr[count3++] += str[arr[3]][j];
//                }
//            }
//        }
//        else
//        {
//            return mystr;
//        }
//        return mystr;
//    }
//};

class Solution 
{
public:
     const char* acLetter2Str[10] = { "", "", "abc", "def", "ghi", "jkl", 
                                      "mno", "pqrs", "tuv", "wxyz" };

     //"abc","def","ghi"
     void letterAdd(string digites, vector<string>& rkVec)
     {
        //3 9
        int before = rkVec.size();
        if (rkVec.empty())
        {
            //len = 3
            for (int i = 0; i < digites.length(); i++)
            {
                rkVec.push_back(string(1, digites[i]));
            }
            //"a"
            //"b"
            //"c"
        }
        else
        {
            //3
            for (int i = 0; i < digites.length(); i++)
            {
                //9
                for (int j = 0; j < before; j++)
                {
                    rkVec.push_back(rkVec[j] + digites[i]);
                }
            }
        }
        rkVec.erase(rkVec.begin(), rkVec.begin() + before);
     }

    //"234"
    vector<string> letterCombinations(string digits) 
    {
        vector<string> retStr;
        //len = 3
        for (int i = 0; i < digits.length(); i++)
        {
            //2 3 4
            letterAdd(acLetter2Str[digits[i] - '0'], retStr);
        }
        return retStr;
    }
};

int main()
{
    return 0;
}